(defvar coins '(1 2 5 10 20 50 100 200))

(defun coins ()
  '(1 2 5 10 20 50 100 200))

(defun maxim (n coins)
  (loop for i in coins collect (floor (/ n i))))

(defun validp (n values coins)
  (= n (valueof values coins)))

(defun list-valueof(values coins)
  (loop for v in values 
     for c in coins 
     collect (* v c)))

(defun valueof(values coins)
  (loop for i in values 
     for j in coins sum (* i j)))

(defun generate-next(values max  coins)
  (cond 
    ((null values) (list '1))
    (t (if (> (valueof values coins) max)
	   (cons '0 (generate-next (cdr values) max coins))
	   (cons  (+ 1 (car values)) (cdr values))))))

(defun ismax(values maxims)
  (and (>= (length values) (length maxims)) (>= (car (last values)) (car (last maxims)))))

(defun probl31(max)
  (loop with coins = (coins)
     with maxims = (maxim max coins)
     with ways = 0
     for current = (generate-next nil max coins) then (generate-next current max coins)
     until (ismax current maxims)
     when (validp max current coins)
     do (incf ways)
     finally (return ways)))

(defun num-ways (amount coins)
  (cond ((zerop amount) 1)
	((or (< amount 0) (null coins)) 0)
	(t (+ (num-ways amount (cdr coins))
	      (num-ways (- amount (car coins)) coins)))))
(print
 (num-ways 200 '(1 2 5 10 20 50 100 200))